Expand description
hibitset
Provides hierarchical bit sets, which allow very fast iteration on sparse data structures.
What it does
A BitSet may be considered analogous to a HashSet<u32>. It
tracks whether or not certain indices exist within it. Its
implementation is very different, however.
At its root, a BitSet relies on an array of bits, which express
whether or not indices exist. This provides the functionality to
add( ) and remove( ) indices.
This array is referred to as Layer 0. Above it, there is another
layer: Layer 1. Layer 1 acts as a ‘summary’ of Layer 0. It contains
one bit for each usize bits of Layer 0. If any bit in that usize
of Layer 0 is set, the bit in Layer 1 will be set.
There are, in total, four layers. Layers 1 through 3 are each a a summary of the layer immediately below them.
Example, with an imaginary 4-bit usize:
Layer 3: 1------------------------------------------------ ...
Layer 2: 1------------------ 1------------------ 0-------- ...
Layer 1: 1--- 0--- 0--- 0--- 1--- 0--- 1--- 0--- 0--- 0--- ...
Layer 0: 0010 0000 0000 0000 0011 0000 1111 0000 0000 0000 ...This method makes operations that operate over the whole BitSet,
such as unions, intersections, and iteration, very fast (because if
any bit in any summary layer is zero, an entire range of bits
below it can be skipped.)
However, there is a maximum on index size. The top layer (Layer 3)
of the BitSet is a single usize long. This makes the maximum index
usize**4 (1,048,576 for a 32-bit usize, 16,777,216 for a
64-bit usize). Attempting to add indices larger than that will cause
the BitSet to panic.
Structs
BitSet but allows setting of value
without unique ownership of the structureIterator over a BitSetLike structure.ParallelIterator over a BitSetLike structure.BitSet.BitSet is a simple set designed to track which indices are placed
into it.BitSetAll is a bitset with all bits set. Essentially the same as
BitSetNot(BitSet::new()) but without any allocation.BitSetAnd takes two BitSetLike items, and merges the masks
returning a new virtual set, which represents an intersection of the
two original sets.BitSetNot takes a BitSetLike item, and produced an inverted virtual set.
Note: the implementation is sub-optimal because layers 1-3 are not active.BitSetOr takes two BitSetLike items, and merges the masks
returning a new virtual set, which represents an merged of the
two original sets.BitSetXor takes two BitSetLike items, and merges the masks
returning a new virtual set, which represents an merged of the
two original sets.Iterator over a DrainableBitSet structure.Traits
BitSetLike-like types.BitSetLike trait which allows draining it.